package leetcode.Hot100;

import java.util.HashSet;

/**
 * @author Cheng Jun
 * Description: 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 * <p>
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 * <p>
 * 你可以认为每种硬币的数量是无限的。
 * <p>
 * 链接：https://leetcode-cn.com/problems/coin-change
 * @version 1.0
 * @date 2021/11/19 6:55
 * @see wordBreak1
 * Tencent 二面题，面试题
 * @see coinChange1
 */
@Deprecated
// 这种解法时间复杂度是 O(n^2) 其中n是 amount。时间复杂度极高，提交LeetCode超时，所以废弃。学习 coinChange1 的解法
public class coinChange {
    static boolean canChange = false;

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11));
    }

    // DP思路：定义 f(n) 为 整数 amount 所需的最小硬币数，则 f(n-1) 为整数 amount-1 所需的最小硬币数，如果f(n) 不能由coins 凑出来就是 -1。
    // 那么， f(n) = min {f(j) >= 0 ? f(j): break + coinsSet.contains(i - j)? 1 : }
    public static int coinChange(int[] coins, int amount) {
        // 数组转成 Set，有利用查询 某个数存不存在
        HashSet<Integer> coinsSet = new HashSet<>();
        for (int coin : coins) {
            coinsSet.add(coin);
        }
        // 0 到 amount 有 amount+1 个数，coinsNum[n] 就是 f(n)，
        int[] coinsNum = new int[amount + 1];
        // amount 为0 时，coinsNum[0] 就是 0，这也是动态规划的初始值
        coinsNum[0] = 0;
        for (int i = 1; i <= amount; i++) {
            // DP 的动态规划转移方程
            // f(n) = min {f(j) >= 0 ? f(j): break + coinsSet.contains(i - j)? 1 : }
            for (int j = 0; j < i; j++) {
                // coinsNum[j] 必须有意义， -1代表不能凑出 j ,并且 i-j 的剩余部分 必须在 coinsSet中
                if (coinsNum[j] >= 0 && coinsSet.contains(i - j)) {
                    if (coinsNum[i] > 0) {
                        coinsNum[i] = Math.min(coinsNum[i], coinsNum[j] + 1);
                    } else {
                        coinsNum[i] = coinsNum[j] + 1;
                    }
                } else {
                    // 如果 为0 表示，没有被设置过（数组的出示值）, 不为 0 的话，该是多少还是多少
                    coinsNum[i] = coinsNum[i] == 0 ? -1 : coinsNum[i];
                }
            }
            // 上面的 fori 会超时。下面我们从 可用零钱数的角度进行 内循环，减少 较大的amount 带来的循环消耗。
            for (int j = 0; j < coins.length; j++) {

            }
        }
        return coinsNum[amount];
    }


}
